package LeetCode;

import java.util.Arrays;

/**
 * @Author: Dijah
 * @Date: 2023/1/10 18:13
 * @Desc:
 * 差分数组
 */
public class code1109_corpFlightBookings {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] ans = new int[n];
        //构造差分数组
        Difference diff = new Difference(ans);
        for(int [] booking:bookings){
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            diff.increment(i,j,val);
        }
        return diff.result();
    }
    class Difference{

        private int [] diff;

        public Difference(int [] nums){
            int n = nums.length;
            diff = new int[n];
            //根据初始值构造差分数组
            diff[0] = nums[0];
            for(int i = 1; i<nums.length;i++){
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        //给区间[i,j]增加val （可以是负数）
        public void increment(int i , int j ,int val){
            diff[i] += val;
            if(j + 1 < diff.length){
                diff[j + 1] -= val;
            }
        }

        //返回结果数组
        public int [] result(){
            int [] res = new int [diff.length];
            res[0] = diff[0];
            //根据差分数组构造结果数组
            for(int i = 1; i< diff.length; i++){
                res[i] = res[i-1] + diff[i];
            }
            return res;
        }
    }

    public static void main(String[] args) {
        code1109_corpFlightBookings corp = new code1109_corpFlightBookings();
        int [][] bookings =  {{1,2,10},{2,3,20},{2,5,25}};
        int n = 5;

        int[] ints = corp.corpFlightBookings(bookings, n);
        for (int anInt : ints) {
            System.out.println(anInt);
        }

    }


}


